#include "IO.h"
#include <cctype>
#include <cstdio>
#define DEBUG
char gc()
{
#ifdef DEBUG
	return getchar();
#endif

	#define BUFFER_SIZE (1<<20)
	static char buf[BUFFER_SIZE], *p1, *p2;
	if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, BUFFER_SIZE, stdin);
	return p1 == p2 ? ' ' : *p1++;
}
static int stk[100],top=0;
void putint(int x,char end) // 快速输出
{
	if(x<0) putchar('-'),x=-x;
	if(!x) putchar('0');
	else
	{
		while(x) stk[++top]=x%10,x/=10;
		while(top) putchar(stk[top]+'0'),top--;
	}
	if(end) putchar(end);
}
int getint() // 快读
{
	char c=gc();int x=0;bool sgn=0;
	while(!isdigit(c)&&c!='-') c=gc();
	if(c=='-') sgn=1,c=gc();
	while(isdigit(c)) x=x*10+c-'0',c=gc();
	if(sgn) x=-x;
	return x;
}